package leetcode_200;

import helpclass.TreeNode;

/**
 *@author 周杨
 *BinaryTreeMaximumPathSum_124 返回至少一个节点的最长路径  可以不经过根节点
 *describe:用递归
 *2018年5月25日 下午7:03:15
 */
public class BinaryTreeMaximumPathSum_124_ {
	private int max = Integer.MIN_VALUE;
	public static void main(String[] args) {
		BinaryTreeMaximumPathSum_124_ test=new BinaryTreeMaximumPathSum_124_();
		TreeNode root=new TreeNode(1);
		root.left=new TreeNode(2);
		root.right=new TreeNode(3);
		System.out.println(test.maxPathSum(root));

	}
	public int maxPathSum(TreeNode root) {
		 help(root);
	     return max;
    }
	
	public int help(TreeNode root) {
		if(root == null) return 0;
        int left = Math.max(0,help(root.left));//只有0才可能入列
        int right = Math.max(0,help(root.right));
        max = Math.max(max,root.val+left+right);
        return root.val+Math.max(left,right);	//返回以以此节点为根的最长路径长度 但只取一条 是为了路径不能走到两边
	}

}
